#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def sqrt(self, x):
        # return a most largest number a, which a * a < x
        if x in [0, 1]:
            return x

        left, right = 0, x

        while left < right-1:
            mid = (left + right) // 2
            square = mid ** 2
            if  square == x:
                return mid
            if square < x:
                left = mid
            else:
                right = mid

        return left


def main():
    print("start main")
    s = Solution()
    ret = s.sqrt(1)
    print(ret)

if __name__ == "__main__":
    main()
